#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define OK  1
#define ERROR  0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int  Status;

typedef char  ElemType;
typedef struct BiTNode{
  ElemType data;
  struct BiTNode *lchild,*rchild;//左右孩子指针
} BiTNode,*BiTree;

Status CreateBiTree(BiTree &T) {  // 算法6.4
  // 按先序次序输入二叉树中结点的值（一个字符），’#’字符表示空树，
  // 构造二叉链表表示的二叉树T。
  char ch;
  scanf("%c",&ch);
  if (ch=='#') T = NULL;
  else {
    if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;
      T->data=ch; // 生成根结点
      CreateBiTree(T->lchild); // 构造左子树
      CreateBiTree(T->rchild); // 构造右子树
  }
  return OK;
} // CreateBiTree

int NodeCount0(BiTree T)
{
    if(T)
    {
    if(T->rchild==NULL&&T->lchild==NULL)
        return NodeCount0(T->rchild)+NodeCount0(T->lchild)+1;
    else return NodeCount0(T->rchild)+NodeCount0(T->lchild);
    }
    return 0;
}

int NodeCount1(BiTree T)
{
    if(T)
    {
    if((T->rchild&&T->lchild==NULL)||(T->rchild==NULL&&T->lchild))
        return NodeCount1(T->rchild)+NodeCount1(T->lchild)+1;
    else return NodeCount1(T->rchild)+NodeCount1(T->lchild);
    }
    else return 0;
}

int NodeCount2(BiTree T)
{
    if(T)
    {
    if(T->rchild&&T->lchild)
        return NodeCount2(T->rchild)+NodeCount2(T->lchild)+1;
    else return NodeCount2(T->rchild)+NodeCount2(T->lchild);
    }
    else return 0;
}

int main()   //主函数
{
  BiTNode *T;
  CreateBiTree(T);
   printf("%d\n",NodeCount2(T));
   printf("%d\n",NodeCount1(T));
   printf("%d",NodeCount0(T));
  //补充代码
}//main
